package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_130_被围绕的区域 {
    //测试
    public static void main(String[] args) {
        char[][] chars = null;
//        chars=new char[][]{{'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'}};
//        chars=new char[][]{
//                {'O','X','O','O','X','O','X','O','O','O'},
//                {'O','O','O','O','O','X','O','O','X','O'},
//                {'O','O','O','O','O','O','O','O','X','O'},
//                {'O','O','O','O','O','O','X','X','X','O'},
//                {'O','O','O','O','O','X','O','O','O','X'},
//                {'O','O','O','O','O','O','O','O','O','X'},
//                {'O','O','O','O','X','O','O','O','O','O'},
//                {'O','O','O','O','X','O','O','O','X','O'},
//                {'X','X','O','O','O','O','O','O','O','O'},
//                {'O','O','O','O','X','O','X','O','O','X'}};
//        chars=new char[][]{{'O','O','O'},{'O','O','O'},{'O','O','O'}};
//        chars=new char[][]{{'X','O','X','O','X','O'},{'O','X','O','X','O','X'},{'X','O','X','O','X','O'},{'O','X','O','X','O','X'}};
        chars=new char[][]{{'X','O','X','X'},{'O','X','O','X'},{'X','O','X','O'},{'O','X','O','X'},{'X','O','X','O'},{'O','X','O','X'}};
        new 力扣_130_被围绕的区域().solve(chars);
        System.out.println(chars);
    }

    /**
    题目：给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，
          并将这些区域里所有的 'O' 用 'X' 填充。

     示例 1：
     输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
     输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
     解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。
     任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

     示例 2：
     输入：board = [["X"]]
     输出：[["X"]]

    分析：【PR 💗💗💗💗💗】
       1.DFS深度优先遍历 ：找到位'O'的字符，记录此处已经被遍历，
                           情况：a.周围全是'X'则：改变为X
                                b.在边缘，则跳过
                                c.周围还有'X'：向下深度递归查找，返回最底层是否是被包围
                            --需要回溯？
                            boolean[][] see ：记录走过的位置，
                            boolean[][] ok ：记录这些位置是可以出去的
       2.广度优先遍历：总队列+ 扫描队列： 边缘找到节点"O"，然后扫描上下左右的"O"加入当前扫描队列
                                          弹出队列，改为占位符"#",循环扫描队列循环扫描附近'O'，再度遍历将O->X，将#->O
            --执行用时：2 ms, 在所有 Java 提交中击败了46.16%的用户
       3.深度优先遍历：侵入式，找到边缘的o,上下递归的找其它0，并标记走过，最后再遍历一遍整个地图，为‘O’,但没有走过的 置为X
            -- 执行用时：1 ms, 在所有 Java 提交中击败了99.93%的用户

    边界值 & 注意点：
       1.
     **/
    public void solve(char[][] board) {
            // 2.广度优先遍历：总队列+ 扫描队列： 边缘找到节点"O"，然后扫描上下左右的"O"加入当前扫描队列
            int row =board.length-1,clo=board[0].length-1;
            Deque<int[]> deque =new ArrayDeque<>();
            for (int i = 0; i < board[0].length; i++) {//第1行，最后一行
                if(board[0][i]=='O'){
                    board[0][i] = '#';
                    deque.add(new int[]{0,i});
                }
                if(board[row][i]=='O'){
                    board[row][i] = '#';
                    deque.add(new int[]{row,i});
                }
            }
            for (int i = 0; i < board.length; i++) {//第1列，最后一列
                if(board[i][0]=='O'){
                    board[i][0] = '#';
                    deque.add(new int[]{i,0});
                }
                if(board[i][clo]=='O'){
                    board[i][clo] = '#';
                    deque.add(new int[]{i,clo});
                }
            }
            int[][] xy = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};  //四个方向的横纵坐标点变化
            while (!deque.isEmpty()){
                int[] point = deque.pollLast();
                int x = point[0],y = point[1];
                for (int a = 0; a < xy.length; a++) {
                    int newX = x + xy[a][0];
                    int newY = y + xy[a][1];
                    if (newX >= 0 && newX <board.length  && newY >= 0 && newY < board[0].length
                            && board[newX][newY] == 'O') {//【改变为占位符
                        board[newX][newY] = '#';
                        deque.add(new int[]{newX,newY});
                    }
                }
            }
            for (int x = 0; x <= row; x++) {
                for (int y = 0; y <= clo; y++) {
                    if(board[x][y]=='O') board[x][y]='X';
                    if(board[x][y]=='#') board[x][y]='O';
                }
            }

        // 3.深度优先遍历：侵入式，找到边缘的o,上下递归的找其它0，并标记走过，最后再遍历一遍整个地图，为‘O’,但没有走过的 置为X
      /*  boolean[][] see =new boolean[board.length][board[0].length];//记录遍历过的节点
        int row =board.length-1,clo=board[0].length-1;
        for (int i = 0; i < board[0].length; i++) {//第1行，最后一行
            if(board[0][i]=='O'&& !see[0][i])
                dsf(board,0,i,see);
            if(board[row][i]=='O' && !see[row][i])
                dsf(board,row,i,see);
        }
        for (int i = 0; i < board.length; i++) {//第1列，最后一列
            if(board[i][0]=='O'&&!see[i][0])
                dsf(board,i,0,see);
            if(board[i][clo]=='O' && !see[i][clo])
                dsf(board,i,clo,see);
        }
        for (int x = 1; x < row; x++) {
            for (int y = 1; y < clo; y++) {
               if(board[x][y]=='O'&& !see[x][y])
                 board[x][y]='X';
            }
        }*/
    }
    //找到周围的节点，并记录走过的路
    private void dsf(char[][] board, int x, int y, boolean[][] see) {
        if(x<0 ||x==board.length || y<0||y==board[0].length || see[x][y] || board[x][y]=='X') return;
        see[x][y]=true;
        dsf(board,x-1,y,see);
        dsf(board,x+1,y,see);
        dsf(board,x,y-1,see);
        dsf(board,x,y+1,see);
    }
}
